[BAEKJOON] 14699. 관악산 등산

Posted on October 09, 2020

문제 :

서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미래를 보고 답해 주기로 했다.

관악산의 등산로는 1부터 N까지의 서로 다른 번호가 붙어 있는 N개의 쉼터와 두 쉼터 사이를 오갈 수 있는 M개의 길들로 이루어져 있다. Corea는 지면에서부터 산을 오르는 것은 너무 귀찮다고 생각했기 때문에, 케이블카를 타고 임의의 쉼터에서 내린 다음 등산을 시작하기로 했다. Corea는 항상 더 높은 곳을 지향하기 때문에, 쉼터에 도착하면 그 쉼터와 직접 연결된 더 높은 쉼터로 향하는 길들 중 하나를 골라서 그 길을 따라 이동한다. 만약 그런 길이 없다면 등산을 마친다.

관악산의 쉼터들에는 조국의 미래를 볼 수 있는 전망대가 하나씩 설치되어 있다. Corea는 최대한 많은 쉼터를 방문해서 조국의 미래를 많이 보고 Unused에게 전해 주기로 했다. 관악산의 지도가 주어질 때, Corea가 각각의 쉼터에서 출발해서 산을 오를 때 최대 몇 개의 쉼터를 방문할 수 있는지 구하여라.

입력 :

첫 번째 줄에 등산로에 있는 쉼터의 수 N(2 ≤ N ≤ 5, 000)과 두 쉼터 사이를 연결하는 길의 수 M(1 ≤ M ≤ 100, 000)이 주어진다.

두 번째 줄에는 각 쉼터의 높이를 나타내는 N개의 정수가 번호 순서대로 주어진다. 각 쉼터의 높이는 1 이상 1, 000, 000 이하이며 서로 다르다.

세 번째 줄부터 M개의 줄에 걸쳐 각각의 길이 연결하는 두 쉼터의 번호가 공백으로 구분되어 주어진다. 쉼터의 번호는 1 이상 N 이하의 정수이다. 양 끝점이 같은 쉼터인 길은 없으며, 임의의 두 쉼터를 연결하는 길이 여러 개 존재할 수 있다.

출력 :

N개의 줄에 걸쳐 n번째 줄에 Corea가 n번 쉼터에서 출발해서 산을 오를 때 최대로 방문할 수 있는 쉼터의 개수를 출력한다.

풀이 :

최근 알고리즘 2 과목에서 종만북으로 수업을 진행하고 있어 종만북으로 알고리즘 공부를 병행하고 있다. 이번 주차에는 DP를 수업에서 다루고 있는데 내가 DP에 많이 약하구나 하는 것을 많이 느끼고 있는 한 주가 지나가고 있다..

우선 DP의 경우 나는 반복적 동적 계획법(반복문을 사용하는 형태)밖에 사용해 본 적이 없었다. 반복적 동적 계획법의 경우 정확하게 점화식을 세우거나 반복 부분을 확실히 파악하지 않으면 문제를 풀어나가기가 여간 쉽지 않았다. 하지만 완전 탐색을 이용한 재귀 동적 계획법의 경우 기존에 완전 탐색의 로직에서 불필요한 반복 부분을 메모이제이션 배열에 저장해두어 효과적으로 시간복잡도를 줄여나가는 방식이였다.

우선 접근 방법이 훨씬 쉬었기 때문에 이런 방식도 연습을 많이 해보자 싶어 당분간은 세그먼트 트리와 DP를 중심으로 풀어볼 생각이다. 물론 알고 스터디는 다른 문제를 풀더라도!

본 문제 또한 전형적으로 완전 탐색을 진행하며 DP를 사용하면 쉽게 풀 수 있는 문제였다. 각 쉼터마다 더 오를 수 있는 횟수를 각각 저장해두어 빠른 시간안에 답을 구하도록 구현했다.

코드 :

코드 보기/접기

#include <iostream>
#include <vector>
#include <algorithm>
#define vec2 vector<vector<int>>

using namespace std;
int* height, * dp;
vec2 route;

int findFuture(int shelter) {
    if (dp[shelter]) return dp[shelter];

    int i, size = route[shelter].size(), cur = height[shelter], next;
    for (i = 0; i < size; i++) {
        next = route[shelter][i];
        if (cur < height[next]) dp[shelter] = max(dp[shelter], findFuture(next));
    }
    return ++dp[shelter];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m, i, fir, sec;
    cin >> n >> m;
    height = new int[n + 1]{ 0 };
    dp = new int[n + 1]{ 0 };
    route.resize(n + 1);
    for (i = 1; i <= n; i++)
        cin >> height[i];
    for (i = 0; i < m; i++) {
        cin >> fir >> sec;
        route[fir].push_back(sec);
        route[sec].push_back(fir);
    }
    for (i = 1; i <= n; i++)
        cout << findFuture(i) << '\n';
    return 0;
}

Algorithm

algorithm baekjoon C++